package com.ztom.top100;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

/**
 * 合并 k 个升序链表
 * <p>
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/
 *
 * @author ZhangTao
 */
public class Code14MergeKLists {

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 小根堆弹出多个链表小的头结点
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists1(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
        heap.addAll(Arrays.stream(lists).filter(Objects::nonNull).collect(Collectors.toList()));

        // 哨兵
        ListNode dummy = new ListNode(-1);
        // 当前节点
        ListNode node = dummy;
        while (!heap.isEmpty()) {
            ListNode poll = heap.poll();
            node.next = poll;
            node = node.next;
            if (poll.next != null) {
                heap.add(poll.next);
            }
        }

        return dummy.next;
    }

    /**
     * 数据量较大, 使用分治
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        return process(lists, 0, lists.length - 1);
    }

    private ListNode process(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        int mid = l + ((r - l) >> 1);
        ListNode l1 = process(lists, l, mid);
        ListNode l2 = process(lists, mid + 1, r);
        return mergeTwoLists(l1, l2);
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}
